package com.gofaraway.service.左神算法课;

import java.util.Arrays;

/**
 * @author ChenPeng
 * @Date 2024/12/15 17:21
 */
public class Code02_Sort1 {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    //插入排序
    //依次保证 0-i位置的有序
    //斗地主 抓牌时 就是用的插入排序
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int curr = i; curr > 0; curr--) {
                if (arr[curr] < arr[curr - 1]) {
                    swap(arr, curr - 1, curr);
                }
            }

        }

    }

    //冒泡排序：
    //依次交换 找到最大值
    public static void bubble(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //0 - n-1
        //0 - n-2
        //0 - n-3
        int n = arr.length;
        for (int end = n - 1; end >= 0; end--) {
            // 0 1 ; 1 2; 2 3; end-1 end
            for (int second = 1; second <= end; second++) {
                if (arr[second - 1] > arr[second]) {
                    swap(arr, second - 1, second);
                }
            }
        }
    }

    //选择排序：
    //找到最小值 然后依次交换
    public static void selectorSort(int[] arr) {
        //考虑边界
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        // 0 - n-1
        // 1 - n-1
        // 2 - n-1
        //外层循环 指定最小值要插入的位置
        for (int i = 0; i < n; i++) {
            int minValueIndex = i;
            //内层循环 找到最小值所在的位置
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minValueIndex]) {
                    minValueIndex = j;
                }
            }
            //交换
            swap(arr, i, minValueIndex);
        }
    }


//    public static void main(String[] args) {
//        int[] arr = {2, 51, 4, 5, 8, 4, 6, 1, 0};
//        print(arr);
//        insertSort(arr);
//        print(arr);
//    }

    private static void print(int[] arr) {
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }




    public static void  mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        f(arr, 0, arr.length - 1);
    }

    private static void f(int[] arr, int L, int R) {

        if (L >= R) {
            return;
        }

        int mid = (L + R) / 2;

        // L ... mid arrL  mid +1  ...  R  arrR

         f(arr, L, mid);
         f(arr, mid + 1, R);
        merge1(arr, L, R, mid);

    }

    private static void merge1(int[] arr, int L, int R, int mid) {
        int[] temp = new int[R - L + 1];

        int index = 0;

        int curR = mid +1;


        int curL = L;

        while (curL <= mid &&  curR <= R) {
            if (arr[curL] <= arr[curR]) {
                temp[index] = arr[curL];
                curL++;
                index++;
            } else {
                temp[index] = arr[curR];
                curR++;
                index++;
            }
        }

        while (curL <= mid) {
            temp[index++] =  arr[curL++];
        }

        while (curR <= R) {
            temp[index++] =  arr[curR++];
        }

      for (int i = 0; i < temp.length; i++) {
        arr[L+i] = temp[i];
      }
    }

    private static int[] merge(int[] arrL, int[] arrR) {

        int[] temp = new int[arrR.length + arrL.length];

        int L = 0;
        int R = 0;

        int index = 0;

        while (L <= arrL.length - 1 &&  R <= arrR.length - 1) {
            if (arrL[L] <= arrR[R]) {
                temp[index] = arrL[L];
                L++;
                index++;
            } else {
                temp[index] = arrR[R];
                R++;
                index++;
            }
        }

        while (L <= arrL.length - 1) {
            temp[index++] =  arrL[L++];
        }

        while (R <= arrR.length - 1) {
            temp[index++] =  arrR[R++];
        }

        return temp;
    }


    /**
     * 快速排序
     *
     * @param arr
     */
    public static  void quiteSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        g(arr, 0, arr.length - 1);

    }

    private static void g(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] eq = p(arr, L, R);
        g(arr, L, eq[0] - 1);
        g(arr, eq[1] + 1, R);
    }

    public static void  splitNum(int[] arr, int L, int R) {
        int lessIndex = -1;
        int cur = L;
        int moreIndex = R;

        while ( cur  <= moreIndex ) {
            if (arr[R] < arr[cur]) {
                lessIndex++;
                cur ++;
            } else if (arr[R] > arr[cur]) {
                swap(arr, cur, moreIndex - 1);
                moreIndex--;
            } else {
                cur ++;
            }
        }
        swap(arr, R, moreIndex);
    }

    public static int[] p(int[] arr, int L, int R) {

        int lessIndex = -1;
        int cur = L;
        int moreIndex = R;

        while ( cur  <= moreIndex ) {
            if (arr[R] < arr[cur]) {
                lessIndex++;
                cur ++;
            } else if (arr[R] > arr[cur]) {
                swap(arr, cur, moreIndex - 1);
                moreIndex--;
            } else {
                cur ++;
            }
        }
        swap(arr, R, moreIndex);

        return new int[] {lessIndex + 1, moreIndex};

    }

    public static void spitArr(int[] arr) {

        if (arr == null || arr.length <= 2) {
            return;
        }

        int R = arr.length - 1;

        int pre = -1;
        int index = 0;

        while (index < R) {
            if (arr[index] <= arr[R]) {
                swap(arr, pre+1 , index);
                pre++;
                index++;
            } else {
                index++;
            }
        }
        swap(arr, pre + 1, R);
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1, 5,2,8,3, 1,3,8, 54,2,8,7};
//        spitArr2(arr, 0, arr.length -1);
//        int[] partition = partition(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(partition));
////        spitArr(arr);
//
//        for (int i : arr) {
//            System.out.println(i);
//        }

        System.out.println(Math.pow(2, 3));

        ggg(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static void ggg(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }

        int[] partition = partition(arr, L, R);
        ggg(arr, L,  partition[0] -1);
        ggg(arr, partition[1] +1,  R);
    }


    public static void spitArr2(int[] arr, int L, int R) {
        if (arr == null || arr.length <= 2) {
            return;
        }

        int pre =  L -1;
        int index = L;
        int P = R;

        while (index < P ) {
            if (arr[index] < arr[R]) {
                swap(arr, pre+1 , index);
                pre++;
                index++;
            } else if (arr[index] > arr[R]) {
                swap(arr, P -1, index);
                P--;
            } else {
                index++;
            }
        }

        swap(arr, P, R);
    }


    public static int[] partition(int[] arr, int L, int R) {

        int pre =  L -1;
        int index = L;
        int P = R;

        while (index < P ) {
            if (arr[index] < arr[R]) {
                swap(arr, pre+1 , index);
                pre++;
                index++;
            } else if (arr[index] > arr[R]) {
                swap(arr, P -1, index);
                P--;
            } else {
                index++;
            }
        }

        swap(arr, P, R);


        return new int[] {pre +1,P };
    }


}
